<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>
<body>
  <script>
    var exist = function(board, word) {
        // m 和 n 保存矩阵 行数、列数
        const [m, n] = [board.length, board[0].length];
        // i为当前行索引，j为当前列索引，k为当前需要匹配的单词对应字符的下标
        const dfs = (i, j, k) => {
            // 如果超出矩阵，或者矩阵当前字符和下一个要匹配的字符不相等，跳出递归
            if (i<0 || j<0 || i>m-1 || j>n-1 || board[i][j] !== word[k]) return false;
            // 如果已经匹配字符数等于单词长度，说明匹配成功，返回true
            if (k === word.length-1) return true;

            // 保存当前矩阵元素
            let temp = board[i][j];
            // 设为空表示该位置已经访问过
            board[i][j] = '';
            // 递归上下左右四个方向
            let res = dfs(i+1, j, k+1) || dfs(i, j+1, k+1) || dfs(i-1, j, k+1) || dfs(i, j-1, k+1)
            // 发生回溯之后，将当前已经设为空的字符，还原
            board[i][j] = temp;
            // 将之前的结果一步步返回
            return res;
        }
        // 遍历矩阵每一个字符，都作为起点尝试开始遍历
        for (let i=0; i<m; i++) {
            for (let j=0; j<n; j++) {
                let ans = dfs(i, j, 0);
                // 只要有一次遍历返回了true，则说明至少有一个匹配成功的，返回true
                if (ans === true) return ans;
            }
        }
        // 遍历结束都没返回true，那么返回false
        return false;
    };
  </script>
</body>
</html>